#ifndef BTREE_H
#define BTREE_H

/*
 *	btree.h
 *	Declares prototypes for the binary search tree. Note
 *	we use a doubly-linked binary tree to migrate from
 *	recursive to iterative traversal methods.
 */

#include "bt_data.h"
#include "trend.h"

/* We use a doubly-linked binary search tree to simplify the
 * process of performing traversals and deletions. Using this
 * scheme we do not require use of a stack for iterative 
 * traversals. */
typedef struct _btree_node {
	BTData data;
	struct _btree_node *left;
	struct _btree_node *right;
	struct _btree_node *parent;
} * BTreeNode;

typedef struct _btree {
	int size;
	BTreeNode root;
} * BTree;

/* Initialize a btree with an element returning a pointer
 * to the binary tree. */
BTree btree_init (BTData);

/* Insert a new element into the binary search tree, returns
 * -1 if unsuccessful, 0 if successful or 1 if the key already
 * exists. */
int btree_insert (BTree, char *, FreqField);

/* Search for a specific value in the binary tree and returns the
 * corresponding node. */
BTreeNode btree_lookup (BTree, char *);

/* Remove a key from the binary tree. Note the removal function
 * removes the entire node (as well as frequency statistics).
 * Returns the BTdata element stored at the node. To decrement the
 * frequency of a node, one can call btree_lookup() and pass the BTdata
 * element to btdata_increment(). */
BTData btree_remove (BTree, char *);

/* Free allocated memory in the binary tree, furthermore calculate
 * the differences in the frequency fields and pass those values to
 * the trending function. */
void btree_free (BTree *, TrendingList);

#endif
